// 给定一个二叉树，返回它的 后序 遍历

#include<bits/stdc++.h>
using namespace std;


struct TreeNode
{
    /* data */
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x),left(nullptr),right(nullptr){};
};


class Solution
{
private:
    /* data */
public:
    vector<int> postorderTraversal(TreeNode* root){
        vector<int> res;
        if(root==nullptr){
            return res;
        }

        stack<TreeNode*> sta1;
        stack<TreeNode*> sta2;
        sta1.push(root);
        while (!sta1.empty())
        {
            /* code */
            root = sta1.top();
            sta1.pop();

            sta2.push(root);
            
            if(root->left!=nullptr){
                sta1.push(root->left);
            }
            if(root->right!=nullptr){
                sta1.push(root->right);
            }
        }

        while(!sta2.empty()){
            res.emplace_back(sta2.top()->val);
            sta2.pop();
        }
        return res;
        
    }
};



int main(int argc, char const *argv[])
{
    /* code */
    TreeNode* root = new TreeNode(1);
    root->right=new TreeNode(2);
    root->right->left=new TreeNode(3);

    Sulotion s;
    vector<int> res = s.postorderTraversal(root);

    for(auto i:res){
        cout<<i<<" ";
    }

    delete root->right->left;
    delete root->right;
    delete root;
    return 0;
}
